// 
// impressionistDoc.cpp
//
// It basically maintain the bitmap for answering the color query from the brush.
// It also acts as the bridge between brushes and UI (including views)
//

#include <FL/fl_ask.H>
#include <cmath>
#include <vector>
#include <queue>
#include <time.h>

#include "impressionistDoc.h"
#include "impressionistUI.h"

#include "ImpBrush.h"
#include "OriginalView.h"
#include "fibheap.h"

#define INITIAL 0
#define ACTIVE 1
#define EXPANDED 2
// Include individual brush headers here.
//#include "PointBrush.h"

// Include PixelNode here.
#include "PixelNode.h"


#define DESTROY(p)	{  if ((p)!=NULL) {delete [] p; p=NULL; } }

const int x[] = {1,1,0,-1,-1,-1,0,1};
const int y[] = {0,-1,-1,-1,0,1,1,1};

const int mx[] = {1,0,-1,0};
const int my[] = {0,-1,0,1};

ImpressionistDoc::ImpressionistDoc() 
{
	// Set NULL image name as init. 
	m_imageName[0]	='\0';	

	m_nWidth		= -1;
	m_ucBitmap		= NULL;
	m_ucPainting	= NULL;
	cost_graph		= NULL;
	m_debugPixelNode= NULL;
	m_debugCostLink = NULL;
	m_imageWithContour = NULL;
	m_mask			= NULL;
	m_fragment		= NULL;
	m_seedPoints.clear();
	closedContour.clear();

	m_currentPaintMode = kPaintOriginal;

	// create one instance of each brush
	/*ImpBrush::c_nBrushCount	= NUM_BRUSH_TYPE;
	ImpBrush::c_pBrushes	= new ImpBrush* [ImpBrush::c_nBrushCount];

	ImpBrush::c_pBrushes[BRUSH_POINTS]	= new PointBrush( this, "Points" );

	// Note: You should implement these 5 brushes.  They are set the same (PointBrush) for now
	ImpBrush::c_pBrushes[BRUSH_LINES]				
		= new PointBrush( this, "Lines" );
	ImpBrush::c_pBrushes[BRUSH_CIRCLES]				
		= new PointBrush( this, "Circles" );
	ImpBrush::c_pBrushes[BRUSH_SCATTERED_POINTS]	
		= new PointBrush( this, "Scattered Points" );
	ImpBrush::c_pBrushes[BRUSH_SCATTERED_LINES]		
		= new PointBrush( this, "Scattered Lines" );
	ImpBrush::c_pBrushes[BRUSH_SCATTERED_CIRCLES]	
		= new PointBrush( this, "Scattered Circles" );

	// make one of the brushes current
	m_pCurrentBrush	= ImpBrush::c_pBrushes[0];
	*/
}


//---------------------------------------------------------
// Set the current UI 
//---------------------------------------------------------
void ImpressionistDoc::setUI(ImpressionistUI* ui) 
{
	m_pUI	= ui;
}

//---------------------------------------------------------
// Returns the active picture/painting name
//---------------------------------------------------------
char* ImpressionistDoc::getImageName() 
{
	return m_imageName;
}

//---------------------------------------------------------
// Called by the UI when the user changes the brush type.
// type: one of the defined brush types.
//---------------------------------------------------------
/*void ImpressionistDoc::setBrushType(int type)
{
	m_pCurrentBrush	= ImpBrush::c_pBrushes[type];
}
*/
//---------------------------------------------------------
// Returns the size of the brush.
//---------------------------------------------------------
/*int ImpressionistDoc::getSize()
{
	return m_pUI->getSize();
}
*/
//---------------------------------------------------------
// Load the specified image
// This is called by the UI when the load image button is 
// pressed.
//---------------------------------------------------------
int ImpressionistDoc::loadImage(char *iname) 
{
	m_currentPaintMode = kPaintOriginal;
	// try to open the image to read
	unsigned char*	data;
	int				width, 
					height;

	if ( (data=readBMP(iname, width, height))==NULL ) 
	{
		fl_alert("Can't load bitmap file");
		return 0;
	}

	// reflect the fact of loading the new image
	m_nWidth		= width;
	m_nPaintWidth	= width;
	m_nHeight		= height;
	m_nPaintHeight	= height;

	m_scale			= 1.0;
	m_seedPoints.clear();

	// release old storage
	if ( m_ucBitmap ) delete [] m_ucBitmap;
	if ( m_ucPainting ) delete [] m_ucPainting;
	if ( cost_graph ) delete [] cost_graph;

	m_ucBitmap		= data;

	// allocate space for draw view
	m_ucPainting	= new unsigned char [width*height*3];
	memset(m_ucPainting, 0, width*height*3);

	/*m_pUI->m_mainWindow->resize(m_pUI->m_mainWindow->x(), 
								m_pUI->m_mainWindow->y(), 
								width*2, 
								height+25);*/
	// calculate the cost graph
	cost_graph = new PixelNode [width*height];
	cal_cost_graph();
	
	// calculate the DEBUG pixel node arrays
	m_debugPixelNode = new unsigned char [width*height*3*9];
	memset(m_debugPixelNode, 255, width*height*3*9);
	cal_debug_pixel_node();

	// calculate teh DEBUG cost link array
	m_debugCostLink = new unsigned char [width * height * 3 * 9];
	memset (m_debugCostLink, 0,  width*height*3*9);
	cal_debug_cost_link();

	// display it on origView
	m_pUI->m_origView->resizeWindow(width, height);	
	m_pUI->m_origView->refresh();

	printf("loading image: %d %d\n",width, height);

	// refresh paint view as well
//	m_pUI->m_paintView->resizeWindow(width, height);	
//	m_pUI->m_paintView->refresh();

	return 1;
}


//----------------------------------------------------------------
// Save the specified image
// This is called by the UI when the save image menu button is 
// pressed.
//----------------------------------------------------------------
int ImpressionistDoc::saveImage(char *iname) 
{

	writeBMP(iname, m_nPaintWidth, m_nPaintHeight, m_ucPainting);

	return 1;
}

//----------------------------------------------------------------
// Save the DEBUG pixel graph
// This is called by the UI when the save pixel graph menu button is 
// pressed.
//----------------------------------------------------------------
int ImpressionistDoc::savePixelGraph(char *iname) 
{
	if (!m_debugPixelNode)  return 0;
	writeBMP(iname, m_nWidth*3 , m_nHeight*3 , this->m_debugPixelNode);

	return 1;
}

int ImpressionistDoc::saveCostLinkGraph(char *iname) 
{
	if (!m_debugCostLink)  return 0;
	writeBMP(iname, m_nWidth*3 , m_nHeight*3 , this->m_debugCostLink);

	return 1;
}

int ImpressionistDoc::saveContour(char *iname){
	
	if(!m_ucBitmap ) return 0;
	if (m_imageWithContour) delete [] m_imageWithContour;

	// superimpose contour to original image, saved in m_imageWithContour
	m_imageWithContour = new unsigned char [m_nWidth * m_nHeight * 3];
	memcpy(m_imageWithContour,m_ucBitmap,m_nWidth *m_nHeight * 3 * sizeof(unsigned char));
	for(list<Point>::iterator it = closedContour.begin();it!=closedContour.end();it++){
		Point pt = *it;
		int x = pt.x, y= pt.y;
		m_imageWithContour [3 * (y *m_nWidth + x)] = 255;
		m_imageWithContour [3 * (y *m_nWidth + x)+1] = 0;
		m_imageWithContour [3 * (y *m_nWidth + x)+2] = 0;
	}

	writeBMP(iname, m_nWidth, m_nHeight, this->m_imageWithContour);

	return 1;
}



// call this function to calculate mask matrix for a closed contour
// we do not check if the contour is closed; if not, the algorithm produces weird result
int ImpressionistDoc::generateMask(){
	if(!m_ucBitmap ) return 0;
	if (m_mask)		delete []m_mask;
	m_mask = new bool [m_nWidth * m_nHeight];
	memset (m_mask, 0, m_nWidth * m_nHeight);
	
	for(list<Point>::iterator it = closedContour.begin();it!=closedContour.end();it++){
		Point pt = *it;
		int x = pt.x, y= pt.y;
		m_mask [y * m_nWidth + x] =1;
	}
	
	queue<Point> q;
	Point p;
	//insert boundary point if they are not the contour
	for (int y = 0; y < m_nHeight; ++y) {
		if ( !m_mask[y * m_nWidth]) {
			m_mask[y * m_nWidth] = 1;
			q.push(Point(0,y));
		}	
		if (!m_mask[y * m_nWidth+ m_nWidth -1]) {
			m_mask[ y * m_nWidth + m_nWidth - 1] = 1;
			q.push(Point(m_nWidth-1,y));
		}		
	}
	for (int x = 0; x < m_nWidth; ++x){
		if (!m_mask[x]) {
			m_mask[x] = 1;
			q.push(Point(x,0));
		}
		if ( !m_mask[(m_nHeight -1) * m_nWidth + x]) {
			m_mask[(m_nHeight - 1) * m_nWidth + x] = 1;
			q.push(Point(x,m_nHeight-1));
		}
	}
	int x , y , index, tx,ty, tindex;
	//bfs
	while (q.size() > 0) {
		p = q.front();
		x = p.x;
		y = p.y;
		for (int k = 0; k < 4; ++k) {
			tx = x + mx[k];
			ty = y + my[k];
			if (in_valid_range(ty,tx)) {
				tindex = ty * m_nWidth + tx;
				if (!m_mask[tindex]) {
					m_mask[tindex] = 1;
					q.push(Point(tx,ty));
				}
			}
		}
		q.pop();
	}
}

int ImpressionistDoc::saveMask (char* iname){
	this->generateMask();
	
	if(m_fragment) delete []m_fragment;
	m_fragment = new unsigned char [m_nWidth * m_nHeight * 3];
	memcpy(m_fragment,m_ucBitmap,m_nWidth *m_nHeight * 3 * sizeof(unsigned char));

	for (int h =0; h<m_nHeight; h++){
		for (int w =0; w<m_nWidth; w++){
			// if the pixel is outside of contour, set to (0,0,0)
			if ( m_mask[h * m_nWidth +w]){
				for (int k=0;k<3;k++)	m_fragment[3 * (h *m_nWidth + w) +k] =0;
			}
			else {
				for (int k=0;k<3;k++)	m_fragment[3 * (h *m_nWidth + w) +k] =255;
			}
		}
	}

	writeBMP(iname, m_nWidth, m_nHeight, this->m_fragment);

	return 1;
}

//----------------------------------------------------------------
// Clear the drawing canvas
// This is called by the UI when the clear canvas menu item is 
// chosen
//-----------------------------------------------------------------
int ImpressionistDoc::clearCanvas() 
{

	// Release old storage
	if ( m_ucPainting ) 
	{
		delete [] m_ucPainting;

		// allocate space for draw view
		m_ucPainting	= new unsigned char [m_nPaintWidth*m_nPaintHeight*3];
		memset(m_ucPainting, 0, m_nPaintWidth*m_nPaintHeight*3);

		// refresh paint view as well	
		//m_pUI->m_paintView->refresh();
	}
	
	return 0;
}

//------------------------------------------------------------------
// Get the color of the pixel in the original image at coord x and y
//------------------------------------------------------------------
GLubyte* ImpressionistDoc::GetOriginalPixel( int x, int y )
{
	if ( x < 0 ) 
		x = 0;
	else if ( x >= m_nWidth ) 
		x = m_nWidth-1;

	if ( y < 0 ) 
		y = 0;
	else if ( y >= m_nHeight ) 
		y = m_nHeight-1;

	return (GLubyte*)(m_ucBitmap + 3 * (y*m_nWidth + x));
}

//----------------------------------------------------------------
// Get the color of the pixel in the original image at point p
//----------------------------------------------------------------
GLubyte* ImpressionistDoc::GetOriginalPixel( const Point p )
{
	return GetOriginalPixel( p.x, p.y );
}

//----------------------------------------------------------------
// Calculate the cost graph
//----------------------------------------------------------------
void ImpressionistDoc::cal_cost_graph() {
	double d0,d1,d2,d3;
	double maxD = -1;
	// Calculate link cost
	for (int j = 0; j < m_nHeight; ++j) {
		for (int i = 0; i < m_nWidth; ++i) {
			int index = j * m_nWidth + i;
			cost_graph[index].linkCost[0] = get_horizontal_link_cost(i,j,i+1,j);
			cost_graph[index].linkCost[1] = get_diagonal_link_cost(i,j,i+1,j-1);
			cost_graph[index].linkCost[2] = get_vertical_link_cost(i,j,i,j-1);
			cost_graph[index].linkCost[3] = get_diagonal_link_cost(i,j,i-1,j-1);
			cost_graph[index].linkCost[4] = get_horizontal_link_cost(i,j,i-1,j);
			cost_graph[index].linkCost[5] = get_diagonal_link_cost(i,j,i-1,j+1);
			cost_graph[index].linkCost[6] = get_vertical_link_cost(i,j,i,j+1);
			cost_graph[index].linkCost[7] = get_diagonal_link_cost(i,j,i+1,j+1);
			/*
			d0 = get_horizontal_link_cost(i,j,i+1,j);
			if (in_valid_range(j,i+1)) {
				cost_graph[j * m_nWidth + i + 1].linkCost[4] = d0; 
			}

			d1 = get_diagonal_link_cost(i,j,i+1,j-1);
			if (in_valid_range(j-1,i+1)) {
				cost_graph[(j-1) * m_nWidth + i + 1].linkCost[5] = d1;
			}

			d2 = get_vertical_link_cost(i,j,i,j-1);
			if (in_valid_range(j-1,i)) {
				cost_graph[(j-1) * m_nWidth + i].linkCost[6] = d2;
			}

			d3 = get_diagonal_link_cost(i,j,i-1,j-1);
			if (in_valid_range(j-1,i-1)) {
				cost_graph[(j-1) * m_nWidth + i - 1].linkCost[7] = d3;
			}

			cost_graph[index].linkCost[0] = d0;
			cost_graph[index].linkCost[1] = d1;
			cost_graph[index].linkCost[2] = d2;
			cost_graph[index].linkCost[3] = d3;
			*/
			for (int k = 0; k < 8; ++k )
				if (cost_graph[index].linkCost[k] > maxD)
					maxD = cost_graph[index].linkCost[k];
		}
	}
	printf("maxD is %lf\n",maxD);
	// Initialize the attributes based on the link cost
	double length[8];
	for (int k = 0; k < 8; ++k) {
		length[k] = (k % 2 == 0) ? 1 : sqrt(2.0);
		//printf("%lf ",length[k]);
	}
	for (int j = 0; j < m_nHeight; ++j) {
		for (int i = 0; i < m_nWidth; ++i) {
			int index = j * m_nWidth + i;
			cost_graph[index].column = i;
			cost_graph[index].row = j;
			for (int k = 0; k < 8; ++k) {
				cost_graph[index].linkCost[k] = (maxD - cost_graph[index].linkCost[k]) * length[k];
			}
		}
	}
}

double ImpressionistDoc::get_horizontal_link_cost(int x1, int y1, int x2, int y2) {
	double dd = 0;
	double d[3];
	if (in_valid_range(y1+1,x2) && in_valid_range(y1-1,x2)) {
		GLubyte* color1 = GetOriginalPixel(x1,y1-1);
		GLubyte* color2 = GetOriginalPixel(x2,y1-1);
		GLubyte* color3 = GetOriginalPixel(x1,y1+1);
		GLubyte* color4 = GetOriginalPixel(x2,y1+1);
		for (int k = 0; k < 3; ++k) {
			d[k] = (int)color1[k] + (int)color2[k] - (int)color3[k] - (int)color4[k];
			dd += d[k] * d[k];
		}
		dd = sqrt(dd/48);
	}
	return dd;
}

double ImpressionistDoc::get_vertical_link_cost(int x1, int y1, int x2, int y2) {
	double dd = 0;
	double d[3];
	if (in_valid_range(y2,x1-1) && in_valid_range(y2,x1+1)) {
		GLubyte* color1 = GetOriginalPixel(x1-1,y1);
		GLubyte* color2 = GetOriginalPixel(x1-1,y2);
		GLubyte* color3 = GetOriginalPixel(x1+1,y1);
		GLubyte* color4 = GetOriginalPixel(x1+1,y2);
		for (int k = 0; k < 3; ++k) {
			d[k] = (int)color1[k] + (int)color2[k] - (int)color3[k] - (int)color4[k];
			dd += d[k] * d[k];
		}
		dd = sqrt(dd/48);
	}
	return dd;
}

double ImpressionistDoc::get_diagonal_link_cost(int x1, int y1, int x2, int y2) {
	double d,dr,dg,db;
	if (in_valid_range(y2,x2)) {
		GLubyte* color1 = GetOriginalPixel(x2,y1);
		GLubyte* color2 = GetOriginalPixel(x1,y2);
		dr = (int)color1[0] - (int)color2[0];
		dg = (int)color1[1] - (int)color2[1];
		db = (int)color1[2] - (int)color2[2];
		d = sqrt(1.0 * (dr * dr + dg * dg + db * db) / 6);
	}
	else
		d = 0;
	return d;
}

//----------------------------------------------------------------
// Check whether a point is within the range
//----------------------------------------------------------------
bool ImpressionistDoc::in_valid_range(int j, int i) {
	if (j < 0 || j >= m_nHeight)
		return false;
	if (i < 0 || i >= m_nWidth)
		return false;
	return true;
}

void ImpressionistDoc::refresh() {
	if (m_ucBitmap) {
		m_pUI->m_origView->refresh();
	}
}


//----------------------------------------------------------------
// Calculate the DEBUG Pixel Node and Cost Link arrays
//----------------------------------------------------------------

void ImpressionistDoc::cal_debug_pixel_node (){
	for (int h = 0; h <m_nHeight; h++){
		int new_h = (h * 3 + 1);		// new_h is meaningful in the DEBUG array
		for (int w = 0 ; w < m_nWidth; w++){
			int new_w = w* 3 + 1;
			m_debugPixelNode[ new_h * m_nWidth * 9 + new_w*3] = GetOriginalPixel(w,h)[0];//m_ucBitmap[ 3 * (h*m_nWidth + w)];
			m_debugPixelNode[ new_h * m_nWidth * 9 + new_w*3 + 1] =  GetOriginalPixel(w,h)[1];
			m_debugPixelNode[ new_h * m_nWidth * 9 + new_w*3 + 2] =  GetOriginalPixel(w,h)[2];
		}
	} 
}

void ImpressionistDoc::cal_debug_cost_link(){
		for (int h = 0; h <m_nHeight; h++){
		int new_h = (h * 3 + 1);		// new_h is meaningful in the DEBUG array
		for (int w = 0 ; w < m_nWidth; w++){
			int new_w = w* 3 + 1;
			int index = h*m_nWidth + w;		// index is meaningful in bitmap and cost_graph
			for (int i =0; i<3; i++){
				m_debugCostLink [(new_h-1) * m_nWidth * 9 + (new_w * 3 -3 + i)] =  cost_graph[index].linkCost[3];	//topleft
				m_debugCostLink [(new_h-1) * m_nWidth * 9 + (new_w * 3 + i)] =  cost_graph[index].linkCost[2];	//topmiddle
				m_debugCostLink [(new_h-1) * m_nWidth * 9 + (new_w * 3 +3 + i)] =  cost_graph[index].linkCost[1];	//topleft
				m_debugCostLink [new_h * m_nWidth * 9 +(new_w * 3 -3 + i)] = cost_graph[index].linkCost[4];   //middle left
				m_debugCostLink [new_h * m_nWidth * 9 + new_w*3 + i] = GetOriginalPixel(w,h)[i];	//original pixel
				m_debugCostLink [new_h * m_nWidth * 9 +(new_w * 3 +3 + i)] = cost_graph[index].linkCost[0];	//middle right
				m_debugCostLink [(new_h+1) * m_nWidth * 9 + (new_w * 3 -3 + i)] =  cost_graph[index].linkCost[5];	//bottomleft
				m_debugCostLink [(new_h+1) * m_nWidth * 9 + (new_w * 3 + i)] =  cost_graph[index].linkCost[6];	//bottommiddle
				m_debugCostLink [(new_h+1) * m_nWidth * 9 + (new_w * 3 + 3 + i)] =  cost_graph[index].linkCost[7];	//bottomright
			}
		}
	} 
}

bool ImpressionistDoc::empty_seedPoint()
{
	if (m_seedPoints.empty())
		return true;
	else return false;
}

void ImpressionistDoc::add_seedPoint(Point pt)
{
	m_seedPoints.push_back(pt);
}

void ImpressionistDoc::remove_seedPoint()
{
	m_seedPoints.pop_back();
}

void ImpressionistDoc::clear_seedPoint()
{
	m_seedPoints.clear();
}

bool operator<(const PixelNode& a, const PixelNode& b) {
	return a.totalCost > b.totalCost;
}

void ImpressionistDoc::cal_path_tree(Point seed)
{
	PixelNode** cur_node = new PixelNode* [m_nWidth * m_nHeight];	// only the totalcost of cur_node is valid, other correct info in in cost_graph
	FibHeap pq;
	//priority_queue<PixelNode, vector<PixelNode>, cmp_node> pq;
	int column,row,index,r;
	int state;
	int processed = 0, process_total = m_nHeight * m_nWidth;
	// initialize each node to the INITIAL STATES
	for (int j = 0; j < m_nHeight; ++j) {
		for (int i = 0; i < m_nWidth; ++i) {
			cost_graph[j * m_nWidth + i].state = INITIAL;
		}
	}
	// reset the traverse list
	m_traverseList.clear();
	// set the total cost of seed to be zero, and pointing to NULL
	r = seed.y * m_nWidth + seed.x;
	cost_graph[r].totalCost = 0;
	cost_graph[r].prevNode = -1;//NULL;
	cost_graph[r].counter = 0;
	cost_graph[r].state = INITIAL;
	cur_node[r] = new PixelNode(cost_graph[r]);
	//initialize maxCounter
	maxCounter = 0;
	//insert seed into pq;
	pq.Insert(cur_node[r]/*cost_graph[r]*//**new_node*/);
	PixelNode* q = (PixelNode*  )pq.ExtractMin();
	// the loop
	while (q != NULL) {
		//q = pq.top();
		column = q->column;
		row = q->row;
		index = row * m_nWidth + column;
		//printf("current %d %d %lf %d %d\n",column,row,cost_graph[index].totalCost,cost_graph[index].prevNode,cost_graph[index].counter);
		if (cost_graph[index].state != EXPANDED) {
			m_traverseList.push_back(Point(column,row));
			cost_graph[index].state = EXPANDED;
			maxCounter = max(cost_graph[index].counter,maxCounter);
			for (int k = 0; k < 8; ++k) {
				if (in_valid_range(row + y[k],column + x[k])) {
					r = (row + y[k]) * m_nWidth + column + x[k];
					state = cost_graph[r].state;
					//printf("processing %d %d %d ",column+x[k],row+y[k],state);
					if (state != EXPANDED) {
						if (state == INITIAL) {
							cost_graph[r].prevNode = index;//&(cost_graph[index]);
							cost_graph[r].counter = cost_graph[index].counter + 1;
							cost_graph[r].totalCost = cost_graph[index].totalCost + cost_graph[index].linkCost[k];
							cost_graph[r].state = ACTIVE;
							cur_node[r] = new PixelNode(cost_graph[r]);
							//printf("inital %lf",cost_graph[r].totalCost);
							pq.Insert(cur_node[r]);
						}
						else {
							//printf("previous %lf now %lf ",cost_graph[r].totalCost,cost_graph[index].totalCost + cost_graph[index].linkCost[k]);
							if (cost_graph[r].totalCost > cost_graph[index].totalCost + cost_graph[index].linkCost[k]) {
								cost_graph[r].prevNode = index;//&(cost_graph[index]);
								cost_graph[r].counter = cost_graph[index].counter + 1;
								cost_graph[r].totalCost = cost_graph[index].totalCost + cost_graph[index].linkCost[k];
								PixelNode* new_node = new PixelNode(cost_graph[r]);
								//printf("update");
								pq.DecreaseKey(cur_node[r],*new_node);
							}
						}
					}
					//printf("\n");
				}
			}
		}
		//delete q;
		/*int tmp;
		printf("here!\n");
		scanf("%d",&tmp);
		*///pq.pop();
		q = (PixelNode*)pq.ExtractMin();
	}
	printf("done calculating\n");
	
}

list<Point> ImpressionistDoc::cal_min_path(Point end) {
	list<Point> min_path;
	if (end.x < 0 || end.y< 0 || end.x > this->m_nWidth || end.y> this->m_nHeight){
		printf ("end point exceeds valid range: %d %d\n", end.x,end.y);
		return min_path;
	}
	
	int index = end.y * m_nWidth + end.x;
	int p = cost_graph[index].prevNode; // The path starts with the the prevNode of the end node
	// The loop
	while (p != -1) {
		//printf("%d %d %d\n",p, cost_graph[p].column,cost_graph[p].row);
		min_path.push_front( Point(cost_graph[p].column,cost_graph[p].row) );	
		p = cost_graph[p].prevNode;
		//int tmp;
		//scanf("%d",&tmp);
	}
	return min_path;
}